package com.lcm.algorithm.datatest.sort;

import java.util.Arrays;

/**
 * @description: 希尔排序
 * @author: lcm
 * @create: 2020-04-08 16:58
 **/

public class ShellSort {

    public static void main(String[] args) {
        int[] n = new int[]{6, 5, 2, 7, 3, 9, 8, 4, 10, 1,11,8};
        sort(n);
        //sort2(n);
        System.out.println(Arrays.toString(n));
    }

    public static void sort(int[] nums){
        int gap=nums.length;
        while (gap>1){
            gap=gap/2;
            for(int i=0;i+gap<nums.length;i++){
                for(int j=i+gap;j<nums.length;j=j+gap){
                    int x=j-gap;
                    while (x>=0&&nums[j]<nums[x]){
                        x=x-gap;
                    }
                    x=x+gap;
                    if(x!=j){
                        int temp=nums[j];
                        nums[j]=nums[x];
                        nums[x]=temp;
                    }
                }
            }
        }
    }

    public static void sort2(int[] array){
        //希尔排序的增量
        int d=array.length;
        while(d>1) {
            //使用希尔增量的方式，即每次折半
            d=d/2;
            for(int x=0;x<d;x++) {
                for(int i=x+d;i<array.length;i=i+d) {
                    int temp=array[i];
                    int j;
                    for(j=i-d;j>=0&&array[j]>temp;j=j-d) {
                        array[j+d]=array[j];
                    }
                    array[j+d]=temp;
                }
            }
        }
    }

}
